package com.nl.list;

import java.util.Stack;

public class LinkedList<T> {
	
	Node<T> phead;
	int length;
	public static class Node<T>{
		Node<T> next;
		T value;
		public Node(Node<T>next,T value){
			this.next= next;
			this.value = value;
		}
	}

	public LinkedList() {

	}
	
	public void addToTail(T value){
		if(phead==null){
			phead = new Node<T>(null,value);
		}else{
			Node<T> node = phead;
			while(node.next!=null){
				node = node.next;
			}
			node.next=new Node<T>(null,value);
		}
		length++;
	}
	
	public void remove(T value){
		if(phead==null){
			return;
		}
		
		Node<T> node = phead;
		while(node.next!=null && node.next.value!=value){
			node =node.next;
		}
		if(node!=null&&node.next.value==value){
			Node<T> deletedNode = node.next;
			node.next =deletedNode.next;
			deletedNode.next = null;
		}
	}
	
	public void printListReversinglyRecursively(Node<T>node){
		if(phead!=null){
			if(phead.next!=null){
				printListReversinglyRecursively(phead.next);
			}
			System.out.println("\t"+phead.value);
		}
	}

	public void printListReversingly(){
		if(phead!=null){
			Stack<T> stack =new Stack<T>();
			Node<T> node = phead;
			while(node!=null){
				stack.push(node.value);
				node = node.next;
			}
			for(T t:stack){
				System.out.println("\t"+t);
			}
		}
	}
	
	/**
	 * O(1)实现链表节点的删除
	 * @param toBeDeleted
	 * 平均复杂度 ((n-1)O(1)+O(n))/n
	 */
	public void deleteNode(Node<T> toBeDeleted){
		if(toBeDeleted==null ||phead==null){
			return;
		}
		
		//头节点
		if(phead == toBeDeleted){
			phead=toBeDeleted = null;
		}else if(toBeDeleted.next!=null){
			//中间节点
			toBeDeleted.value = toBeDeleted.next.value;
			Node<T> node = toBeDeleted.next;
			toBeDeleted.next = node.next;
			node.next = null;
		}else{
			Node<T> node = phead;
			while(node.next!=toBeDeleted){
				node = node.next;
			}
			node.next = null;
			toBeDeleted.value = null;
		}
	}

}
